package leetcode.editor.cn.dsa17_traversal;
// 给定一个二叉树的根节点 root ，返回它的 中序 遍历。

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeInorderTraversal94_3 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
     }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最优解： 莫里斯遍历
         */
        public List<Integer> inorderTraversal(TreeNode root) {
            // 中序遍历规则：左根右
            List<Integer> res = new ArrayList<>();
            TreeNode exPoint = null; // 当前节点的左子树上中序遍历最后一个结点
            while (root != null) {
                if (root.left == null) {
                    // 1.左子树为空则当前节点加入目标序列，然后指向右子树
                    res.add(root.val);
                    root = root.right;
                } else { // 2.左子树不为空，找到exPoint节点
                    // exPoint节点就是当前节点向左走一步，然后一直向右走至无法走为止
                    // 无法走有两种情况，要么没有右子树，要么就是指向了当前节点(辅助线)
                    exPoint = root.left;
                    while (exPoint.right != null && exPoint.right != root) {
                        exPoint = exPoint.right;
                    }
                    // 2.1 如果exPoint的右子树为空，需要做辅助线，将其连接到当前节点
                    // 因为exPoint作为左子树最后一个访问的节点，下一个节点就是访问根节点，
                    // 也就是当前节点，所以需要先进行连接以方便下一次直接访问
                    // 然后指向左子树，因为左边节点需要先访问
                    if (exPoint.right == null) {
                        exPoint.right = root;
                        root = root.left;
                    } else {
                        // 2.2 如果exPoint的右子树不为空，说明辅助线连好了，exPoint连接了当前节点。
                        // 辅助线的起始元素为左子树最后一个访问的节点，而指向的是当前元素，说明当前节点是通过辅助线过来的，这意味着左子树最后一个节点也访问完毕了
                        // 按照规则，应该访问当前节点，然后指向右子树，同时去除辅助线
                        res.add(root.val);
                        exPoint.right = null;
                        root = root.right;
                    }
                }
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}